package com.spacewiz13.algorithm.search;

/**
 * 二分查找实现。
 * @author David
 *
 */
public class BinSearch {
	
	public static void main(String[] args){
		int[] array = {1,5,7,9,11,12,16,22,44,67};
		System.out.println(BinSearch.binSearch(array, 0, array.length-1, 11));
		System.out.println(BinSearch.binSearch(array, 6));
	}

	/**
	 * 递归查找
	 * @return
	 */
	public static int binSearch(int[] array,int start,int end,int tar){
		int mid = (end-start)/2+start;
		if((end-start)<=0){
			return -1;
		}
		if(array[mid]==tar){
			return mid;
		}else if(array[mid]>tar){
			end = mid-1;
			return BinSearch.binSearch(array, start, end, tar);
		}else if(array[mid]<tar){
			start = mid+1;
			return 	BinSearch.binSearch(array, start, end, tar);
		}
		return -1;
	}
	
	/**
	 * 普通查找
	 * @return
	 */
	public static int binSearch(int[] array,int tar){
		int length = array.length;
		int start = 0;
		int end = length-1;
		while(end>=start){
			int mid = (end-start)/2 + start;
			if(array[mid]==tar){
				return mid;
			}else if(array[mid]>tar){
				end = mid-1;
			}else if(array[mid]<tar){
				start = mid+1;
			}
		}
		return -1;
	}
	
}
